import heapq
class Solution(object):
    def mincostToHireWorkers(self, quality, wage, k):
        n = len(quality)
        st = [[wage[i] / quality[i],quality[i]] for i in range(n)]
        st.sort()
        total = 0
        out = []
        min_val = float('inf')
        for i in range(n):
            heapq.heappush(out, - st[i][1])
            total += st[i][1]
            if len(out) > k:
                node = heapq.heappop(out)
                total += node
            if len(out) == k:
                min_val = min(min_val, total * st[i][0])
        return min_val

